Asymptotic analysis of a leader election algorithms

摘要

Itai and Rodeh showed that, on the average, the communication of a leader election algorithm takes no more than LN bits, where L ≃ 2.441716 and N denotes the size of the ring. We give a precise asymptotic analysis of the average number of rounds M (n) required by the algorithm, proving for example that M (∞) {colon equals} limn → ∞ M (n) = 2.441715879 .where n is the number of starting candidates in the election. Accurate asymptotic expressions of the second moment M(2) (n) of the discrete random variable at hand, its probability distribution, and the generalization to all moments are given. Corresponding asymptotic expansions (n → ∞) are provided for sufficiently large j, where j counts the number of rounds. Our numerical results show that all computations perfectly fit the observed values. Finally, we investigate the generalization to probability t / n, where t is a non-negative real parameter. The real function M (∞, t) {colon equals} limn → ∞ M (n, t) is shown to admit one unique minimumM (∞, t*) on the real segment (0, 2). F urthermore, the variations of M (∞, t) on the whole real line are also studied in detail. © 2006 Elsevier B.V. All rights reserved.